package edu.asu.sapa.utils;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;

// should add buckets for tied priorities.  Helps with multiple effects, conditions, and simul. actions
// change focus from re-using event wrappers to non-modifiable wrappers, and thus fully shareable?
// Only permute the array of references to events, instead of the floats (and the pointers to actual events) themselves?

// With many state copies, there are lots of queues on the same events...

// So I guess StateQ and other queues should have slightly different focus.

// Albeit, a Heap-based priority queue for states/events isn't right in the first place, probably.
// [bucket implementation is probably better...]


public abstract class PriorityQueue<E, T extends Priority<E>> implements
		Cloneable, java.util.Queue<T> {
	public static final int DEFAULT = 8;
	public static final int GROW_BY = 4;
	public static final int RESERVE = 2;

	public int size = 0;
	public T[] table;

	public PriorityQueue() {
		// subclasses have to initialize events;
	}


	// this queue is its own memory pool
	public abstract T newElement();
	
	public boolean add(E event, float p) {
		if (size >= table.length) {
			growArray();
		}
		T t=null;
		if (table[size] == null) {
			t = newElement();
		} else {
			t = table[size];
		}
		t.set(event, p);
		int i = size++;
		int parent;
		for (; (parent = (i - 1) >> 1) >= 0 && t.compareTo(table[parent]) < 0; i = parent) {
			table[i] = table[parent];
		}
		table[i] = t;
		return true;
	}

	public boolean add(T te) {
		if (size >= table.length) {
			growArray();
		}
		int i = size++;
		int parent;
		for (; (parent = (i - 1) >> 1) >= 0 && te.compareTo(table[parent]) < 0; i = parent) {
			table[i] = table[parent];
		}
		table[i] = te;
		return true;
	}

	public boolean addAll(Collection<? extends T> c) {
		if (c == this)
			throw new IllegalArgumentException();
		int csize = c.size();
		if (size + csize > table.length)
			table = Arrays.copyOf(table, size + csize);
		Iterator<? extends T> e = c.iterator();
		if (!e.hasNext())
			return false;
		T te;
		int i, parent;
		do {
			te = e.next();
			i = size++;
			for (; (parent = (i - 1) >> 1) >= 0 && te.compareTo(table[parent]) < 0; i = parent) {
				table[i] = table[parent];
			}
			table[i] = te;
		} while (e.hasNext());

		return true;
	}

	public void clear() {
		// recycle memory aggressively
		size = 0;
	}

	public boolean contains(Object te) {
		for (int i = 0; i < size; ++i) {
			if (table[i].equals(te))
				return true;
		}
		return false;
	}

	public boolean containsAll(Collection<?> c) {
		for (Object o : c) {
			if (!contains(o))
				return false;
		}
		return true;
	}

	// no range checking
	public T delete() {
		int i = 0;
		int child;
		// recycle memory aggressively
		T down_event;
		down_event = table[--size];
		table[size] = table[i];
		// events[i] = down_event; // should be unnecessary
		for (; (child = (i << 1) + 1) < size; i = child) {
			if (child + 1 < size
					&& table[child + 1].compareTo(table[child]) < 0) {
				++child;
			}
			if (table[child].compareTo(down_event) < 0) {
				table[i] = table[child];
			} else {
				break;
			}
		}
		table[i] = down_event;
		return table[size];
	}

	public T element() {
		if (size <= 0)
			throw new NoSuchElementException();
		return table[0];
	}

	// slow growth.
	public void growArray() {
		table = Arrays.copyOf(table, size + GROW_BY);
		//System.out.println(".");
	}

	public boolean isEmpty() {
		if (size == 0)
			return true;
		return false;
	}

	public PriorityQueueIterator iterator() {
		return new PriorityQueueIterator();
	}

	public boolean offer(T te) {
		if (size >= table.length)
			return false;
		int i = size++;
		int parent;
		for (; (parent = (i - 1) >> 1) >= 0 && te.compareTo(table[parent]) < 0; i = parent) {
			table[i] = table[parent];
		}
		table[i] = te;
		return true;
	}

	// events can't be null, but it could (theoretically) have length 0
	// but more importantly, events[0] might not be null if
	// size <= 0
	public T peek() {
		if (size <= 0)
			return null;
		return table[0];
	}

	public T poll() {
		if (size <= 0)
			return null;
		int i = 0;
		int child;
		// recycle memory aggressively
		T down_event;
		down_event = table[--size];
		table[size] = table[i];
		// events[i] = down_event; // should be unnecessary
		for (; (child = (i << 1) + 1) < size; i = child) {
			if (child + 1 < size
					&& table[child + 1].compareTo(table[child]) < 0) {
				++child;
			}
			if (table[child].compareTo(down_event) < 0) {
				table[i] = table[child];
			} else {
				break;
			}
		}
		table[i] = down_event;
		return table[size];
	}

	// no growth, and no range checking.
	// will throw indexoutofbounds, nullpointer, etc.
	public boolean put(T te) {
		int i = size++;
		int parent;
		for (; (parent = (i - 1) >> 1) >= 0 && te.compareTo(table[parent]) < 0; i = parent) {
			table[i] = table[parent];
		}
		table[i] = te;
		return true;
	}

	public T remove() {
		if (size <= 0)
			throw new NoSuchElementException();
		int i = 0;
		int child;
		// recycle memory aggressively
		T down_event;
		down_event = table[--size];
		table[size] = table[i];
		// events[i] = down_event; // should be unnecessary
		for (; (child = (i << 1) + 1) < size; i = child) {
			if (child + 1 < size
					&& table[child + 1].compareTo(table[child]) < 0) {
				++child;
			}
			if (table[child].compareTo(down_event) < 0) {
				table[i] = table[child];
			} else {
				break;
			}
		}
		table[i] = down_event;
		return table[size];
	}

	public boolean remove(Object o) {
		throw new UnsupportedOperationException();
	}

	public boolean removeAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	public boolean retainAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	public int size() {
		return size;
	}

	/**
	 * Maintains Heap-order
	 * 
	 * @see java.util.Collection#toArray(T[])
	 */
	public <T> T[] toArray(T[] a) {
		if (a.length < size) {
			a = Arrays.copyOf(a, size);
		}
		if (a.length > size) {
			a[size] = null;
		}
		if (a == null)
			return (T[]) toArray();
		for (int i = 0; i < size; ++i) {
			a[i] = (T) table[i].clone();
		}
		return a;
	}

	@Override
	public String toString() {
		StringBuilder buf = new StringBuilder(size * 10);
		for (int i = 0; i < size; ++i) {
			buf.append(table[i]).append('\n');
		}
		return buf.toString();
	}

	class PriorityQueueIterator implements Iterator<T> {
		int i = 0;

		public boolean hasNext() {
			return i < size;
		}

		public T next() {
			try {
				return table[i++];
			} catch (Exception e) {
				throw new NoSuchElementException(e.getMessage());
			}
		}

		public void remove() {
			if (i == 0)
				throw new IllegalStateException();
			if (i == 1) {
				remove();
				i = 0;
			}
			throw new UnsupportedOperationException();
		}

	}
}
